// https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <algorithm>


using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
		int len = nums.size();
		if(len <= 2) return len;
		int left = 0, right = 1;
		int flag = 0;
		while(right < len){
			if(nums[left] == nums[right]){
				if(flag == 0){
					flag = 1;
				}else{
					int tmp = left;
					while(tmp < len - 1){
						nums[tmp] = nums[tmp + 1];
						tmp++;
					}
					len--;
					continue;
				}
			}else{
				flag = 0;
			}
			left++;
			right++;
		}
		return len;
    }
	
	// 优化后，可以减少数组移动的次数
	int removeDuplicates1(vector<int>& nums) {
		int len = nums.size();
		if(len <= 2) return len;
		int left = 0, right = 2;
		while(right < len){
			if(nums[left] == nums[right]){
				while(right < len - 1 && nums[right] == nums[right + 1]){
					right++;
				}
				
				left++;
				int tmpL = left;
				int tmpR = right;
				while(tmpR < len){
					nums[tmpL] = nums[tmpR];
					tmpL++;
					tmpR++;
				}
				cout << "left:" << left << endl;
				len -= tmpR - tmpL;
				right = left + 2;
			} else {
				left++;
				right++;
			}
		}
		return len;
    }
	/*
	简单解析：首先i<2的时候肯定我们直接覆盖x的值到i指的位置，如果nums.size()小于等于2在1次或两次遍历后我们也可以得到正确i的值。 在i等于二后我们开始检测此时x是否比i前面两个数大，如果不是的话那么肯定是需要被替换的，这个时候我们继续移动x，i不动，一直这样循环我们就可以得到正确的数组。
*/
	int removeDuplicates2(vector<int>& nums) {
        int i = 0;
        for(int& x : nums){
            if(i < 2 || nums[i-2] < x){
				cout << "i:" << i;
				if(i >= 2)
					cout << ",nums[i-2]:" << nums[i - 2] << ",x:" << x << endl;
				nums[i++] = x;
			} 
		}
        return i;
    }
};

int main(){
	Solution so;
	vector<int> s = {1,1,1,2,2,2,3,3};
	auto res = so.removeDuplicates2(s);
	for(int i = 0; i < res; i++){
		cout << s[i] << ",";
	}
	cout << endl;
	cout << res << endl;
	return 0;
}